package com.liyghting.datastructurealgorithm.binaraysearch;

/**
 * 二分查找 针对有序数据集合的查找算法，查找思想有些类似于分治算法。每次都和待查区间的中点比较，将待查找的区间缩小为原来的一半，
 * 直到找到要查找的元素，或者是待查区间的长度变为0为止。 场景，依赖的数据结构为数组时，时间复杂度为O(logn)，针对的是有序数据，比如如何在 1000
 * 万个整数中快速查找某个整数？ 数据量太小太大都不合适，不过，如果数据之间比较耗时的话，不管数据量大小，推荐使用二分查找， 比如，数组中存储的都是长度超过
 * 300
 *
 * 的字符串，如此长的两个字符串之间比对大小，就会非常耗时。我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势
 * 假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？
 * 
 * @author LiYiGuang
 * @date 2020/1/17 15:46
 */
public class BinarySearch {
	/**
	 * 二分查找，针对有序数据查找，不存在重复数据，循环实现
	 * 
	 * @param arr
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearch(int[] arr, int n, int value) {
		int low = 0;
		int hign = n - 1;

		while (low <= hign) {
			int mid = low + (hign - low) / 2;
			if (arr[mid] == value) {
				return mid;
			}
			if (arr[mid] < value) {
				low = mid + 1;
			} else {
				hign = mid - 1;
			}
		}
		return -1;
	}

	/**
	 * 查找第一个值等于给定值的元素 二分查找，针对有序数据查找，存在重复数据，循环实现
	 * 
	 * @param arr
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearchFirst(int[] arr, int n, int value) {
		int low = 0;
		int hign = n - 1;

		while (low <= hign) {
			int mid = low + (hign - low) / 2;

			if (arr[mid] < value) {
				low = mid + 1;
			} else if (arr[mid] > value) {
				hign = mid - 1;
			} else {
				if (mid == 0 || arr[mid - 1] != value)
					return mid;
				else
					hign = mid - 1;
			}
		}
		return -1;
	}

	/**
	 * 查找最后一个值等于给定值的元素 二分查找，针对有序数据查找，存在重复数据，循环实现
	 *
	 * @param arr
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearchLast(int[] arr, int n, int value) {
		int low = 0;
		int hign = n - 1;

		while (low <= hign) {
			int mid = low + (hign - low) / 2;

			if (arr[mid] < value) {
				low = mid + 1;
			} else if (arr[mid] > value) {
				hign = mid - 1;
			} else {
				if (mid == n - 1 || arr[mid + 1] != value)
					return mid;
				else
					low = mid + 1;
			}
		}
		return -1;
	}

	/**
	 * 查找第一个大于等于给定值的元素 二分查找，针对有序数据查找，存在重复数据，循环实现
	 *
	 * @param arr
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearchFirstGreetEqual(int[] arr, int n, int value) {
		int low = 0;
		int high = n - 1;

		while (low <= high) {
			int mid = low + (high - low) / 2;

			if (arr[mid] < value) {
				low = mid + 1;
			} else {
				if (mid == 0 || arr[mid - 1] < value)
					return mid;
				else
					high = mid - 1;
			}
		}
		return -1;
	}

	/**
	 * 查找最后一个小于等于给定值的元素 二分查找，针对有序数据查找，存在重复数据，循环实现
	 *
	 * @param arr
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearchLastLessEqual(int[] arr, int n, int value) {
		int low = 0;
		int hign = n - 1;

		while (low <= hign) {
			int mid = low + (hign - low) / 2;

			if (arr[mid] <= value) {
				if (mid == n - 1 || arr[mid + 1] > value)
					return mid;
				else
					low = mid + 1;
			} else {
				hign = mid - 1;
			}
		}
		return -1;
	}

	/**
	 * 二分查找，针对有序数据查找，不存在重复数据，递归实现
	 * 
	 * @param arr
	 * @param value
	 * @return
	 */
	public static int bsearch(int[] arr, int value) {
		return bsearchInternally(arr, 0, arr.length - 1, value);
	}

	/**
	 * 有序数组是一个循环有序数组，比如 4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？
	 * 
	 * @param arr
	 * @param value
	 * @return
	 */
	public static int bsearch1(int[] arr, int value) {
		int csize = 0;
		for (int i = 0; i < arr.length; i++) {
			if (i == arr.length - 1 || arr[i] > arr[i + 1]) {
				csize = i + 1;
				break;
			}
		}
		for (int i = 0; i < arr.length / csize; i++) {
			if (arr[i * csize] <= value && arr[(i + 1) * csize - 1] >= value) {
				int low = i * csize;
				int high = (i + 1) * csize - 1;
				while (high >= low) {
					int mid = low + (high - low) / 2;
					if (arr[mid] == value) {
						return mid;
					} else if (arr[mid] > value) {
						high = mid - 1;
					} else {
						low = mid + 1;
					}
				}

			}
		}
		return -1;
	}

	/**
	 * 求一个数据的平方根，精确到小数点后六位
	 * 
	 * @param num
	 * @return
	 */
	public static double squareRoot(double num) {
		double percion = 0.000001;
		double low = 0.0d;
		double hign = num;
		while (hign - low > percion) {
			double mid = low + (hign - low) / 2;
			double value = mid * mid;
			if (Math.abs(mid * mid - num) <= percion) {
				return mid;
			} else if (value > num) {
				hign = mid;
			} else {
				low = mid;
			}

		}
		return -1;
	}

	private static int bsearchInternally(int[] arr, int low, int hign, int value) {
		if (low > hign)
			return -1;
		int mid = low + ((hign - low) >> 1);
		if (arr[mid] == value)
			return mid;
		else if (arr[mid] < value)
			return bsearchInternally(arr, mid + 1, hign, value);
		else
			return bsearchInternally(arr, low, mid - 1, value);
	}

	public static void main(String[] args) {
		// int[] arr = new int[] { 8, 11, 19, 23, 27, 33, 45, 55, 67, 98 };
		// int index = bsearch(arr, 10, 19);
		// System.out.println("index = " + index);
		// index = bsearch(arr, 10, 23);
		// System.out.println("index = " + index);

//		double sr = squareRoot(9);
//		System.out.println("sr = " + sr);

		int[] arr = new int[] { 4,5,6,1,2,3 };
		int index = bsearch1(arr, 4);
		System.out.println("index = " + index);
	}

}
